package leetcode;

/**
 * Created by Ghost on 2014/12/1 0001.
 */
public class Intersection_of_Two_Linked_Lists {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null)
            return null;
        ListNode tmpA = headA;
        int lenA = 0;
        while(tmpA.next!=null){
            lenA++;
            tmpA = tmpA.next;
        }
        lenA++;
        ListNode BrokenPoint = tmpA;
        tmpA.next = headB;
        tmpA = headB.next;
        while(tmpA!=null && headB!=tmpA){
            tmpA = tmpA.next;
        }

        headB = BrokenPoint.next;
        BrokenPoint.next = null;

        if(tmpA==null)
            return null;


        int lenB = 0;
        ListNode tmpB = headB;
        while(tmpB.next!=null){
            lenB++;
            tmpB = tmpB.next;
        }
        lenB++;
        tmpA = headA;
        tmpB = headB;
        if(lenA>lenB){
            int sub = lenA-lenB;
            while(sub>0){
                tmpA = tmpA.next;
                sub--;
            }
        }
        else if(lenB>lenA){
            int sub = lenB-lenA;
            while(sub>0){
                tmpB = tmpB.next;
                sub--;
            }
        }
        while(tmpA!=tmpB){
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }
        return tmpA;
    }

    public static void main(String[] args){
        Intersection_of_Two_Linked_Lists intersection_of_two_linked_lists = new Intersection_of_Two_Linked_Lists();
        ListNode A = new ListNode(1);
        A.next = new ListNode(2);
        A.next.next = new ListNode(3);
        A.next.next.next = new ListNode(4);
        A.next.next.next.next = new ListNode(5);

        ListNode B = new ListNode(6);

        System.out.println(intersection_of_two_linked_lists.getIntersectionNode(A,B).val);
    }
}
